package com.leo.algorithm.linked;

import java.util.PriorityQueue;

public class MergeK {

    public static void main(String[] args) {

    }

    // 合并k个升序链表
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                lists.length, (a, b)->(a.getVal() - b.getVal()));
        // 将 k 个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null)
                pq.add(head);
        }

        while (!pq.isEmpty()) {
            // 获取最小节点，接到结果链表中
            ListNode node = pq.poll();
            p.setNext(node);
            if (node.getNext() != null) {
                pq.add(node.getNext());
            }
            // p 指针不断前进
            p = p.getNext();
        }
        return dummy.getNext();
    }

}
